/*
 * @lc app=leetcode.cn id=923 lang=typescript
 *
 * [923] 三数之和的多种可能
 */

// @lc code=start
function threeSumMulti(arr: number[], target: number): number {
  const twoSumMulti = (arr: number[], l: number, r: number, target: number): number => {
    let res = 0;
    while (l < r) {
      const sum = arr[l] + arr[r];
      if (sum < target) {
        l++;
      } else if (sum > target) {
        r--;
      } else {
        // 前后相等，就是从n个数字中取2个数字的组合数量
        // 表示这是最后一个区间，所以直接返回
        if (arr[l] === arr[r]) {
          const n = r - l + 1;
          res += (n * (n - 1)) / 2;
          res %= modNum;
          break;
        }
        let lcnt = 1;
        let rcnt = 1;
        // arr[l] 相同的数字数量
        while (l < r && arr[l] === arr[l + 1]) {
          l++;
          lcnt++;
        }
        // arr[r] 相同的数字数量
        while (l < r && arr[r] === arr[r - 1]) {
          r--;
          rcnt++;
        }
        // 组合数量
        res += lcnt * rcnt;
        res %= modNum;
        l++, r--;
      }
    }
    return res;
  };
  arr.sort((a, b) => a - b);
  const n = arr.length;
  const modNum = 1e9 + 7;
  let ans = 0;
  // 枚举第一个数，因为后面最少要留两个数字，所以结束条件是n-2
  for (let i = 0; i < n - 2; i++) {
    ans += twoSumMulti(arr, i + 1, n - 1, target - arr[i]);
    ans %= modNum;
  }
  return ans;
}
// @lc code=end
